package com.cb2.algorithm.leetcode;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/clone-graph'>克隆图(Clone Graph)</a>
 * <p>给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。</p>
 * <p>图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
 * <pre>
 * class Node {
 *     public int val;
 *     public List<Node> neighbors;
 * }
 * </pre>
 * </p>
 * <p>给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * <a href='https://leetcode.cn/problems/clone-graph'>查看原题</a>
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>节点数不超过 100 。</li>
 *         <li>每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。</li>
 *         <li>无向图是一个简单图，这意味着图中没有重复的边，也没有自环。</li>
 *         <li>由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。</li>
 *         <li>图是连通图，你可以从给定节点访问到所有节点。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/26 14:56
 */
public class LC0133CloneGraph_M {
    static class Solution {
        public Node cloneGraph(Node node) {
            return cloneGraphByIteration(node);
            //return cloneGraphByRecursion(node);
        }

        private Node cloneGraphByIteration(Node node) {
            if (node == null) {
                return null;
            }
            Map<Node, Node> cloneMap = new HashMap<>();
            Queue<Node> helper = new LinkedList<>();
            // 将第一个节点添加到队列中，用于后续处理邻居节点
            helper.offer(node);
            // 克隆第一个节点并存储到哈希表中
            cloneMap.put(node, new Node(node.val, new ArrayList<>()));
            while (!helper.isEmpty()) {
                Node currNode = helper.poll();
                for (Node neighbor : currNode.neighbors) {
                    if (!cloneMap.containsKey(neighbor)) {
                        helper.offer(neighbor);
                        cloneMap.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                    }
                    // 更新当前节点的邻居列表
                    cloneMap.get(currNode).neighbors.add(cloneMap.get(neighbor));
                }

            }
            return cloneMap.get(node);
        }

        private Node cloneGraphByRecursion(Node node) {
            return dfs(node, new HashMap<>());
        }

        private Node dfs(Node node, Map<Node, Node> cloneMap) {
            if (node == null) {
                return null;
            }
            if (cloneMap.containsKey(node)) {
                return cloneMap.get(node);
            }
            // 克隆节点
            Node cloneNode = new Node(node.val, new ArrayList<>());
            cloneMap.put(node, cloneNode);
            // 处理子节点
            for (Node neighbor : node.neighbors) {
                cloneNode.neighbors.add(dfs(neighbor, cloneMap));
            }
            return cloneNode;
        }
    }

    static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}